package MST.kruskal;

import java.util.Arrays;

/**
 * 最小生成树
 * 解决公交站问题
 */
public class Kruskal {
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 图
     */
    static class MGraph {
        int nums;
        int edgeNums; // kruskal算法中需要对边进行排序选取最小值，所以这里不再用节点个数而是用边的个数
        char[] data; // 各个节点的数据
        int[][] weight; // 邻接矩阵

        /**
         * 初始化
         * @param nums 传入的节点个数
         */
        public MGraph(int nums) {
            this.nums = nums;
            data = new char[nums];
            weight = new int[nums][nums];
        }

        /**
         * 获取节点c的下标
         * @param c
         * @return
         */
        private int getPosition(char c) {
            for (int i = 0; i < nums; i++) {
                if (data[i] == c) {
                    return i;
                }
            }
            return -1;
        }

        /**
         * 获取图中的所有边到时候需要排序用
         * @return
         */
        private Edge[] getEdges() {
            Edge[] edges = new Edge[edgeNums];
            int index = 0;
            for (int i = 0; i < nums; i++) {
                for (int j = i + 1; j < nums; j++) {
                    if (weight[i][j] != INF) {
                        edges[index ++] = new Edge(data[i], data[j], weight[i][j]);
                    }
                }
            }
            return edges;
        }
    }

    /**
     * 边的类
     */
    static class Edge {
        char start, end; // 边的两个端点
        int weight;

        public Edge(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "<" + start +
                    ", " + end +
                    "> [" + weight +
                    ']' + "\t";
        }
    }

    /**
     * 最小生成树
     */
    static class MinTree {
        MGraph mGraph;
        /**
         * 创建图
         * @param mGraph
         * @param data
         * @param weight
         */
        public void creatGraph(MGraph mGraph, char[] data, int[][] weight) {
            int nums = data.length;
            int edgeNums = 0;
            for (int i = 0; i < nums; i++) {
                mGraph.data[i] = data[i];
                for (int j = 0; j < nums; j++) {
                    mGraph.weight[i][j] = weight[i][j];
                    if (weight[i][j] != INF && weight[i][j] != 0) {
                        edgeNums ++;
                    }
                }
            }
            mGraph.edgeNums = edgeNums / 2;
            this.mGraph = mGraph;
        }

        /**
         * 展示图的邻接矩阵
         * @param mGraph
         */
        private void showGraph(MGraph mGraph) {
            System.out.println("邻接矩阵为：");
            // 需要以节点的个数遍历邻接矩阵，而不是边的个数！！！
            for (int i = 0; i < mGraph.data.length; i++) {
                for (int j = 0; j < mGraph.data.length; j++) {
                    System.out.printf("%10d\t", mGraph.weight[i][j]);
                }
                System.out.println();
            }
        }

        /**
         * 对边进行排序（使用冒泡排序）
         * @param edges
         */
        private void sortEdge(Edge[] edges) {
            for (int i = 0; i < edges.length - 1; i++) { // 外层循环控制趟数，最后一次只剩一个元素不用再排序所以edges.length - 1
                for (int j = 0; j < edges.length - 1 - i; j++) { // 内层循环控制比较的两个元素，以及元素的区间
                    if (edges[j].weight > edges[j + 1].weight) {
                        Edge tmp = edges[j];
                        edges[j] = edges[j + 1];
                        edges[j + 1] = tmp;
                    }
                }
            }
        }

        /**
         * 获取下标为i的节点当前的“终点”
         * @param ends 为当前已经访问过的节点集合 0 -- 未加入 1 -- 已加入
         * @param i
         * @return
         */
        private int getEnd(int[] ends, int i) {
            while (ends[i] != 0) {
                i = ends[i];
            }
            return i; // 如果还没有加入这个ends则就是这个下标
        }

        public void kruskal() {
            int[] ends = new int[mGraph.nums]; // 用于保存已有最小生成树的节点用于最后找每个节点的终点
            int index = 0; // 用于对ends数组的设置
            Edge[] rets = new Edge[mGraph.nums - 1]; // n - 1条边
            Edge[] edges = mGraph.getEdges();
            // 首先对边进行排序
            sortEdge(edges);
            System.out.println(Arrays.toString(edges));
            // 遍历edges
            for (Edge edge : edges) {
                // 获取这条边的两个顶点
                int start = mGraph.getPosition(edge.start);
                int end = mGraph.getPosition(edge.end);
                // 获取两个顶点的终点
                int es = getEnd(ends, start);
                int ee = getEnd(ends, end);
                if (es != ee) {
                    // 当他们终点不相同时就可以选择这条边
                    ends[es] = ee;
                    rets[index ++] = edge;
                    System.out.println(edge);
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] data = new char[] {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][] {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}
        };
        MGraph mGraph = new MGraph(7);
        MinTree minTree = new MinTree();
        minTree.creatGraph(mGraph, data, weight);
        minTree.showGraph(mGraph);
        minTree.kruskal();
    }
}
